package 剑指Offer._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/7/18 10:26
 * 剪绳子 II
 * 算法：数学 -- 找规律
 * 需要取余，不能比较了，所以不能使用动态规划来做
 * 数字拆成几个数乘积要最大，结果都是 n 个 2 乘 n 个 3
 */
public class _14II {
    public static void main(String[] args) {
        System.out.println(new _14II().cuttingRope(2));
    }

    public int cuttingRope(int n) {
        if (n == 1) return 0; // 0 * 1
        if (n == 2) return 1; // 1 * 1
        if (n == 3) return 2; // 1 * 2
        long ans = 1; // 这里要用 long 类型，碰到数据大的，就用 long
        while (n > 4) {
            ans = ans * 3;
            ans = ans % 1000000007;
            n -= 3;
        }
        return (int) (ans * n % 1000000007);
    }

}
